import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 20404
 * Date: 2023-01-26
 * Time: 0:01
 */
public class MyLinkedList {
    private int size;

    Node head;

    @Override
    public String toString() {
        return "MyLinkedList{" +
                " " + size +
                ", " + head +
                '}';
    }

    public MyLinkedList(MyLinkedList myLinkedList) {
        this.head = myLinkedList.head;
    }

    public MyLinkedList(int date) {
        this.head = new Node(date);
    }

    public MyLinkedList() {

    }


    public static class Node {
        private int value;
        Node next;

        @Override
        public String toString() {
            return "{" +
                    " " + value +
                    ", " + next +
                    '}';
        }

        public Node(int value) {
            this.value = value;
        }
    }
    public void addFirst(int data) {
        Node first = new Node(data);
        first.next = head;
        head = first;
        size++;
    }

    public void display() {
        Node cur = head;
        System.out.print("[ ");
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }System.out.println("]");
    }
    public void display(Node head) {
        Node cur = head;
        System.out.print("[ ");
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }System.out.println("]");
    }
    public void addLast(int data) {
        if(head == null) {
            head = new Node(data);
            size++;
            return;
        }
        Node cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = new Node(data);
        size++;
    }
    public void addIndex(int index,int data) {
        try {
            checkIndex(index, "Exception from addIndex(...)");
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return;
        }
        Node cur = head;
        Node newOne = new Node(data);
        if(index == 0) {
            addFirst(data);
            return;
        }
        while(--index != 0) {
            cur = cur.next;
        }
        newOne.next = cur.next;
        cur.next = newOne;
        size++;
    }

    private void checkIndex(int index, String str) {
        if(index < 0 || index > size) {
            throw new IndexOutOfException(str);
        }
    }
    public Node getNode(int index) {
        try {
            checkIndex(index, "Exception from getNode(...)");
            Node cur = head;
            while(index-- != 0) {
                cur = cur.next;
            }
            return cur;
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return null;
        }
    }

    private Node searchPreviousOne(int index) {
        try {
            checkIndex(index, "Exception from searchPreviousOne(...)");
        } catch (IndexOutOfException e) {
            e.printStackTrace();
            return null;
        }
        if(index == 0) {
            return null;
        }
        Node cur = head;
        while(--index != 0) {
            cur = cur.next;
        }
        return cur;
    }
    private Node searchPreviousOne(Integer val) {
        int value = val.intValue();
        if (value == head.value || !contains(value)) {
            return null;
        } else {
            Node cur = head;
            while (cur.next != null) {
                if (cur.next.value == value) {
                    return cur;
                } else {
                    cur = cur.next;
                }
            }
        }
        return null;
    }
    public boolean contains(int key) {
        if(head != null) {
            Node cur = head;
            while(cur != null) {
                if(cur.value == key) {
                    return true;
                }else {
                    cur = cur.next;
                }
            }
        }
        return false;
    }
    public void remove(int key) {
        if(contains(key)) {
            size--;
            if(head.value == key) {
                head = head.next;
            }else {
                Node prev = searchPreviousOne(Integer.valueOf(key));
                prev.next = prev.next.next;
            }
        }
    }
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        Node prev = head;
        Node cur = head.next;
        while(cur != null) {
            if(cur.value == key) {
                size--;
                prev.next = cur.next;
            }else {
                prev = cur;
            }cur = cur.next;
        }
        if(head.value == key) {
            size--;
            head = head.next;
        }
    }
    public int size() {
        return this.size;
    }

    public void clear() {
        head = null;
        size = 0;
    }

    public static Node deleteDuplication(Node pHead) {
        Node cur = pHead;
        Node prevNode = null;
        Node prevPrev = pHead;
        boolean flag = true;
        while(cur != null) {
            flag = true;
            if(cur != pHead && cur.value == prevNode.value) {
                flag = false;
                while(cur != null && cur.value == prevNode.value) {
                    cur = cur.next;
                }
                if(prevNode.value != pHead.value) {
                    prevPrev.next = cur;
                }else {
                    pHead = cur;
                }
                if(cur == null) {
                    return pHead;
                }
            }
            if(flag && cur != pHead && (prevPrev.next == null || prevPrev.next.next == null
                    || prevPrev.next.value != prevPrev.next.next.value)) {
                prevPrev = prevPrev.next;
            }
            prevNode = cur;
            cur = cur.next;
        }
        return pHead;
    }



}


/*
//头插法

//尾插法

//任意位置插入,第一个数据节点为0号下标

//查找是否包含关键字key是否在单链表当中

//删除第一次出现关键字为key的节点

//删除所有值为key的节点

//得到单链表的长度
*/



